package org.example.myleet.p413;

/**
 * 动态规划
 * 思考：
 * 计算每个位置的等差数列长度，则该位置上能形成的子数组的数量=(len - 3 + 1)，因为对于长度>=3的任意等差数列
 * 总可以每减少一个左端的长度来增加等差数列的数量
 * 每个位置的等差数列长度则是在公差d相同的情况下，比左边的元素的长度+1
 */
public class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
        if (nums.length < 3) {
            return 0;
        }
        //保存每个位置的等差数列长度
        int[] lenArr = new int[nums.length];
        //保存当前状态的公差
        int d = nums[1] - nums[0];
        lenArr[0] = 1;
        lenArr[1] = 2;
        for (int i = 2; i < nums.length; ++i) {
            //当前位置与上一个位置的公差
            int curD = nums[i] - nums[i - 1];
            if (d != curD) {
                //如果公差不同，说明开启了新的等差数列，并更新公差
                lenArr[i] = 2;
                d = curD;
            } else {
                //如果公差相同，等差数列长度+1
                lenArr[i] = lenArr[i - 1] + 1;
            }
        }
        int count = 0;
        for (int i = 0; i < nums.length; ++i) {
            //每个位置代表的等差数列的长度所能得到的等差数列数量，特别的小于0的时候按0算
            int cnt = lenArr[i] - 3 + 1;
            count += Math.max(cnt, 0);
        }
        return count;
    }
}
